package __1_enumeration;

/*

6
-2 11 -12 13 -5 8

16
---
输出最大连续子序列和，规定最大连续子序列和大于0
序列(-2,11,-4,13,-5,-2)的最大连续子序列和为11 - 4 + 13 = 20
枚举
(-2) (-2,11) (-2,11,-4) ...
(11) (11,-4) (11,-4,13) ...
...
(-2)
---
优化算法后的枚举
(-2)小于0舍去，没必要从-2开始枚举了，因为开局已经低人一等了从这里找不到最大的，
从11开始，(11), (11,-12)又小于0了，舍去
从13开始，(13), (13,-5), (13,-5,8)
那从-5或8开始不就枚举不到了吗？
也没必要了，因为没有加上前面正的序列和，必然是小于前面枚举过的最大连续子序列和了


 */

import java.util.Scanner;

public class __5_MaxContinueSubsequenceSum {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            // 第一代码块
            {
                int maxSubSum = a[0];
                // i,j分别表示子序列的起始和终止位置,0 < i < n-1, i < j < n-1， i,j两层循环即可穷举出所有子序列和
                for (int i = 0; i < n; i++) {
                    int subSum = 0;
                    for (int j = i; j < n; j++) {
                        subSum += a[j];
                        // 找到最大子序列
                        if (subSum > maxSubSum) {
                            maxSubSum = subSum;
                        }
                        // System.out.print(subSum + "_");
                    }
                }
                System.out.println();
                System.out.println(maxSubSum);
                System.out.println("---------------------------------------------");
            }
            // 第二代码块
            {
                // 算法还可以优化
                int maxSubSum = 0;
                int subSum = 0;
                for (int i = 0; i < n; i++) {
                    subSum += a[i];
                    if (subSum < 0) {
                        subSum = 0;
                    }
                    if (subSum > maxSubSum) {
                        maxSubSum = subSum;
                    }
                    // System.out.println(subSum + "," + maxSubSum);
                }
                System.out.println(maxSubSum);
            }
        }
    }
}